<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <title>选择排序</title>
  </head>

  <body>
    <script>
      /*
       * 选择排序（Selection Sort）思路：
       * 例如：数组[3, 2, 4, 1] 进行从小到大排序为例，步骤如下：
       * 1.假定第一位的“3”是最小值。
       * 2.最小值“3”与第二位的“2”进行比较，2小于3，所以新的最小值是第二位的“2”。
       * 3.最小值“2”与第三位的“4”进行比较，2小于4，最小值不变。
       * 4.最小值“2”与第四位的“1”进行比较，1小于2，所以新的最小值是第四位的“1”。
       * 5.第四位的“1”与第一位的“3”互换位置，数组变为[1, 2, 4, 3]。
       * 6.这一轮比较结束后，最小值“1”已经排到正确的位置了，然后对剩下的[2, 4, 3]重复上面的过程。
       * 7.每一轮排序都会将该轮的最小值排到正确的位置，直至剩下最后一个位置，所有排序结束
       */
      var selectionArr = [3, 2, 4, 1];
      console.log("selectionArr=", selectionSort(selectionArr));
      /**
       * array 被排序的数组
       */
      function selectionSort(array) {
        for (let i = 0; i < array.length - 1; i++) {
          //将当前位置设为最小值
          let minIndex = i;

          // 检查数组其余部分是否更小
          for (let j = i + 1; j < array.length; j++) {
            //一次遍历，记录比minIndex更小元素的索引
            if (array[j] < array[minIndex]) {
              minIndex = j;
            }
          }

          //一次遍历后找出最小值，然后与第一个元素交换位置
          if (i !== minIndex) {
            var temp = array[i];
            array[i] = array[minIndex];
            array[minIndex] = temp;
          }
        }
        return array;
      }
    </script>
  </body>
</html>
